package com.Sep_Five;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * 652. 寻找重复的子树
 * 给定一棵二叉树 root，返回所有重复的子树。
 *
 * 对于同一类的重复子树，你只需要返回其中任意一棵的根结点即可。
 *
 * 如果两棵树具有相同的结构和相同的结点值，则它们是重复的。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/find-duplicate-subtrees
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */

public class Solution652 {

    /**
     *map储存次数，将树序列化，利用string builder来进行操作
     */
    Map<String,Integer> map=new HashMap<>();
    List<TreeNode> res=new ArrayList<>();

    public List<TreeNode> findDuplicateSubtrees(TreeNode root) {
        dfs(root);
        return res;
    }

    public String dfs(TreeNode root){
        if(root==null) return " ";
        StringBuilder sb=new StringBuilder();
        sb.append(root.val).append("-");
        sb.append(dfs(root.left)).append(dfs(root.right));
        String key=sb.toString();
        map.put(key,map.getOrDefault(key,0)+1);
        if(map.get(key)==2) res.add(root);
        return key;
    }

    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
}
